/*
 *  dynarray.c
 *  
 *
 *  Created by Bob Dondero
 *  Copyright 2011 CritTer. All rights reserved.
 *
 */

#include "dynarray.h"
#include <assert.h>
#include <stdlib.h>

enum {MIN_PHYS_LENGTH = 2};
enum {GROWTH_FACTOR = 2};

/*--------------------------------------------------------------------*/

/* A DynArray consists of an array, along with its logical and
   physical lengths. */

struct DynArray
{
      /* The number of elements in the DynArray from the client's
         point of view. */
      int iLength;
      
      /* The number of elements in the array that underlies the
         DynArray. */
      int iPhysLength;
      
      /* The array that underlies the DynArray. */
      const void **ppvArray;
};

/*--------------------------------------------------------------------*/

#ifndef NDEBUG
static int DynArray_isValid(DynArray_T oDynArray)
   
/* Check the invariants of oDynArray.  Return 1 (TRUE) iff oDynArray
   is in a valid state. */
   
{
   if (oDynArray->iLength < 0) return 0;
   if (oDynArray->iPhysLength < MIN_PHYS_LENGTH) return 0;
   if (oDynArray->iLength > oDynArray->iPhysLength) return 0;
   if (oDynArray->ppvArray == NULL) return 0;
   return 1;
}
#endif

/*--------------------------------------------------------------------*/

DynArray_T DynArray_new(int iLength)
   
/* Return a new DynArray_T whose length is iLength.
   It is a checked runtime error for iLength to be negative. */
   
{
   DynArray_T oDynArray;
   
   assert(iLength >= 0);
   
   oDynArray = (struct DynArray*)malloc(sizeof(struct DynArray));
   assert(oDynArray != NULL);
   oDynArray->iLength = iLength;
   if (iLength > MIN_PHYS_LENGTH)
      oDynArray->iPhysLength = iLength;
   else
      oDynArray->iPhysLength = MIN_PHYS_LENGTH;
   oDynArray->ppvArray =
      (const void**)calloc((size_t)oDynArray->iPhysLength,
                           sizeof(void*));
   assert(oDynArray->ppvArray != NULL);
   
   return oDynArray;
}

/*--------------------------------------------------------------------*/

void DynArray_free(DynArray_T oDynArray)
   
/* Free oDynArray.  Do nothing if oDynArray is NULL. */
   
{
   if (oDynArray == NULL)
      return;
   
   free(oDynArray->ppvArray);
   free(oDynArray);
}

/*--------------------------------------------------------------------*/

int DynArray_getLength(DynArray_T oDynArray)
   
/* Return the length of oDynArray.
   It is a checked runtime error for oDynArray to be NULL. */
   
{
   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   
   return oDynArray->iLength;
}

/*--------------------------------------------------------------------*/

void *DynArray_get(DynArray_T oDynArray, int iIndex)
   
/* Return the iIndex'th element of oDynArray.
   It is a checked runtime error for oDynArray to be NULL.
   It is a checked runtime error for iIndex to be less than 0 or
   greater than or equal to the length of oDynArray. */
   
{
   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   assert(iIndex >= 0);
   assert(iIndex < oDynArray->iLength);
   
   return (void*)(oDynArray->ppvArray)[iIndex];
}

/*--------------------------------------------------------------------*/

void *DynArray_set(DynArray_T oDynArray, int iIndex,
                   const void *pvElement)
   
/* Assign pvElement to the iIndex'th element of oDynArray.  Return the 
   old element.
   It is a checked runtime error for oDynArray to be NULL.
   It is a checked runtime error for iIndex to be less than 0 or
   greater than or equal to the length of oDynArray. */
   
{
   const void *pvOldElement;
   
   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   assert(iIndex >= 0);
   assert(iIndex < oDynArray->iLength);
   
   pvOldElement = oDynArray->ppvArray[iIndex];
   oDynArray->ppvArray[iIndex] = pvElement;
   return (void*)pvOldElement;
}

/*--------------------------------------------------------------------*/

static void DynArray_grow(DynArray_T oDynArray)
   
/* Double the physical length of oDynArray. */
   
{
   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   
   oDynArray->iPhysLength *= GROWTH_FACTOR;
   oDynArray->ppvArray =
      (const void**)realloc(oDynArray->ppvArray,
                            sizeof(void*) * oDynArray->iPhysLength);
   assert(oDynArray->ppvArray != NULL);
}

/*--------------------------------------------------------------------*/

void DynArray_add(DynArray_T oDynArray, const void *pvElement)
   
/* Add pvElement to the end of oDynArray, thus incrementing its length.
   It is a checked runtime error for oDynArray to be NULL. */
   
{
   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   
   if (oDynArray->iLength == oDynArray->iPhysLength)
      DynArray_grow(oDynArray);
   
   oDynArray->ppvArray[oDynArray->iLength] = pvElement;
   oDynArray->iLength++;
}

/*--------------------------------------------------------------------*/
void DynArray_addAt(DynArray_T oDynArray, int iIndex,
                    const void *pvElement)
   
/* Add pvElement to oDynArray such that it is the iIndex'th element.
   It is a checked runtime error for oDynArray to be NULL. 
   It is a checked runtime error for iIndex to be less than 0 or
   greater than the length of oDynArray. */
   
{
   int i;
   
   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   assert(iIndex >= 0);
   assert(iIndex <= oDynArray->iLength);
   
   if (oDynArray->iLength == oDynArray->iPhysLength)
      DynArray_grow(oDynArray);
   
   for (i = oDynArray->iLength; i > iIndex; i--)
      oDynArray->ppvArray[i] = oDynArray->ppvArray[i-1];
   
   oDynArray->ppvArray[iIndex] = pvElement;
   oDynArray->iLength++;
}

/*--------------------------------------------------------------------*/

void *DynArray_removeAt(DynArray_T oDynArray, int iIndex)
   
/* Remove and return the iIndex'th element of oDynArray.
   It is a checked runtime error for oDynArray to be NULL. 
   It is a checked runtime error for iIndex to be less than 0 or
   greater than or equal to the length of oDynArray. */
   
{
   const void *pvOldElement;
   int i;
   
   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   assert(iIndex >= 0);
   assert(iIndex < oDynArray->iLength);
   
   pvOldElement = oDynArray->ppvArray[iIndex];
   
   oDynArray->iLength--;
   
   for (i = iIndex; i < oDynArray->iLength; i++)
      oDynArray->ppvArray[i] = oDynArray->ppvArray[i+1];
   
   return (void*)pvOldElement;
}

/*--------------------------------------------------------------------*/

void DynArray_toArray(DynArray_T oDynArray, void **ppvArray)
/* Fill ppvArray with the elements of oDynArray.
   It is a checked runtime error for oDynArray or ppvArray to be NULL.
   It is an unchecked runtime error for *ppvArray to be too small
   to hold all elements of oDynArray.  */
   
{
   int i;
   
   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   assert(ppvArray != NULL);
   
   for (i = 0; i < oDynArray->iLength; i++)
      ppvArray[i] = (void*)oDynArray->ppvArray[i];
}

/*--------------------------------------------------------------------*/
   
   void DynArray_map(DynArray_T oDynArray,
                     void (*pfApply)(void *pvElement, void *pvExtra),
                     const void *pvExtra)
   
/* Apply function *pfApply to each element of oDynArray, passing
   pvExtra as an extra argument.  That is, for each element pvElement
   of oDynArray, call (*pfApply)(pvElement, pvExtra).
   It is a checked runtime error for oDynArray or pfApply to be
   NULL. */
   
{
   int i;
   
   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   assert(pfApply != NULL);
   
   for (i = 0; i < oDynArray->iLength; i++)
      (*pfApply)((void*)oDynArray->ppvArray[i], (void*)pvExtra);
}

/*--------------------------------------------------------------------*/

static void DynArray_swap(const void *ppvArray[], int iOne, int iTwo)
   
/* Swap ppvArray[iOne] and ppvArray[iTwo]. */
   
{
   const void *pvTemp;
   pvTemp = ppvArray[iOne];
   ppvArray[iOne] = ppvArray[iTwo];
   ppvArray[iTwo] = pvTemp;
}

/*--------------------------------------------------------------------*/

static int DynArray_partition(const void *ppvArray[],
                              int iLeft, int iRight,
                              int (*pfCompare)(const void *pvElement1, const void *pvElement2))
   
/* Divide ppvArray[iLeft...iRight] into two partitions so elements
   in the first partition are <= elements in the second partition.
   Return the index of the element that marks the partition
   boundary. The sort order is determined by *pfCompare. */
   
/* This function is a variation of the partition() function shown in
   the book "Algorithms in C" by Robert Sedgewick. */
   
{
   int iFirst = iLeft-1;
   int iLast = iRight;
   
   while (1)
   {
      while ((*pfCompare)(ppvArray[++iFirst], ppvArray[iRight]) < 0)
         ;
      while ((*pfCompare)(ppvArray[iRight], ppvArray[--iLast]) < 0)
         if (iLast == iLeft)
            break;
      if (iFirst >= iLast)
         break;
      DynArray_swap(ppvArray, iFirst, iLast);
   }
   DynArray_swap(ppvArray, iFirst, iRight);
   return iFirst;
}

/*--------------------------------------------------------------------*/

static void DynArray_quicksort(const void *ppvArray[],
                               int iLeft, int iRight,
                               int (*pfCompare)(const void *pvElement1, const void *pvElement2))
   
/* Sort ppvArray[iLeft...iRight] in ascending order, as determined
   by *pfCompare. */
   
/* This function is a variation of the quicksort() function shown in
   the book "Algorithms in C" by Robert Sedgewick. */
   
{
   int iMid;
   if (iRight > iLeft)
   {
      iMid = DynArray_partition(ppvArray, iLeft, iRight, pfCompare);
      DynArray_quicksort(ppvArray, iLeft, iMid - 1, pfCompare);
      DynArray_quicksort(ppvArray, iMid + 1, iRight, pfCompare);
   }
}

/*--------------------------------------------------------------------*/

void DynArray_sort(DynArray_T oDynArray,
                   int (*pfCompare)(const void *pvElement1, const void *pvElement2))
   
/* Sort oDynArray in the order determined by *pfCompare.
 *pfCompare should return <0, 0, or >0 depending upon whether
 *pvElement1 is less than, equal to, or greater than *pvElement2,
 respectively.
 It is a checked runtime error for oDynArray or pfCompare to be
 NULL. */
   
{
   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   assert(pfCompare != NULL);
   
   DynArray_quicksort(oDynArray->ppvArray, 0, oDynArray->iLength-1,
                      pfCompare);
}

/*--------------------------------------------------------------------*/

int DynArray_search(DynArray_T oDynArray, void *pvSoughtElement,
                    int (*pfCompare)(const void *pvElement1, const void *pvElement2))
   
/* Linear search oDynArray for *pvSoughtElement using *pfCompare to
   determine equality.  Return the index at which *pvSoughtElement
   is found, or -1 if there is no such index.
   *pfCompare should return 0 if *pvElement1 is equal to pvElement2,
   and non-0 otherwise.
   It is a checked runtime error for oDynArray or pfCompare to be
   NULL. */
   
{
   int i;
   
   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   assert(pfCompare != NULL);
   
   for (i = 0; i < oDynArray->iLength; i++)
      if ((*pfCompare)(oDynArray->ppvArray[i], pvSoughtElement) == 0)
         return i;
   return -1;
}

/*--------------------------------------------------------------------*/

int DynArray_backwardsSearch(DynArray_T oDynArray, void *pvSoughtElement,
                    int (*pfCompare)(const void *pvElement1, const void *pvElement2))
/* Linear search oDynArray for *pvSoughtElement using *pfCompare to
   determine equality.  Return the index at which *pvSoughtElement
   is found, or -1 if there is no such index.
   *pfCompare should return 0 if *pvElement1 is equal to pvElement2,
   and non-0 otherwise.
   It is a checked runtime error for oDynArray or pfCompare to be
   NULL. */
   
{
   int i;
   
   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   assert(pfCompare != NULL);
   
   for (i = oDynArray->iLength-1; i > 0; i--)
      if ((*pfCompare)(oDynArray->ppvArray[i], pvSoughtElement) == 0)
         return i;
   return -1;
}


/*--------------------------------------------------------------------*/

int DynArray_bsearch(DynArray_T oDynArray, void *pvSoughtElement,
                     int (*pfCompare)(const void *pvElement1, const void *pvElement2))
/* Binary search oDynArray for *pvSoughtElement using *pfCompare to
   determine equality.  Return the index at which *pvSoughtElement
   is found, or -1 if there is no such index.
   *pfCompare should return <0, 0, or >0 depending upon whether
   *pvElement1 is less than, equal to, or greater than *pvElement2,
   respectively.
   It is a checked runtime error for oDynArray or pfCompare to be
   NULL.
   It is an unchecked runtime error for oDynArray not to be sorted
   as determined by *pfCompare. */
   
{
   int iLeft;
   int iRight;
   int iMid;
   int iCompare;
   
   assert(oDynArray != NULL);
   assert(DynArray_isValid(oDynArray));
   assert(pfCompare != NULL);
   
   iLeft = 0;
   iRight = oDynArray->iLength - 1;
   
   while (iLeft <= iRight)
   {
      iMid = (iLeft + iRight) / 2;
      iCompare =
         (*pfCompare)(pvSoughtElement, oDynArray->ppvArray[iMid]);
      if (iCompare == 0)
         return iMid;
      if (iCompare < 0)
         iRight = iMid - 1;
      else
         iLeft = iMid + 1;
   }
   
   return -1;
}
